CSE 444 Final
December 8, 2000
2:30pm – 4:20pm
Name___________________________________
Total number of points:
100
Total time: 1h 50’
1.
[30
points] Consider the E/R diagram below:
a.
[5 points] Considering the Buys relationship, we know that
each purchase is for the benefit of a single employee, and is approved by a
single manager. Add arrows to the diagram to indicate this situation. Also,
indicate whether the arrows capture faithfully this information.
b.
[5 points] Continue to assume the constraint at point a.
Create a relational schema to represent this data by giving the SQL statements
for creating the tables. The statements should include all primary and foreign
keys. The following information is known about the attribute domains: id
consists of 10 characters, phone has 10 characters, name has up
to 30 characters, level is an integer, amount is an integer, and purchaseNo
has 20 characters.
c. [10 points] Write SQL queries to compute the following:
i.
Employee Smith is a high spender. For each manager, compute
the total amount of all purchases approved by that manager for the benefit of
Smith. Your query should print the manager id, name and the total amount of
purchases approved
ii.
Find all purchases in which the approving manager and the beneficiary
employee are the same person. List the purchase number, the purchase amount,
and the name of the employee (manager).
d. [10 points] John, a new database administrator had a bad day: he accidentally deleted all tuples in the Manager table. Help John recover the lost data. Specifically, write a sequence of SQL statements that will populate the Manager table by using other information in the database. The following information about the company helps you recover the data:
i. Each manager manages at least one employee
ii.
The level of a manager is defined as follows. Managers
that manage only regular employees (i.e. that are not managers) have level=1.
Managers that manage only regular employees and managers of level 1 have
level=2, etc. John knows that the highest manager in the company is the CEO and
his level is 4.
2. [20 points]
a. [10 points] Let X,Y be sets of attributes of a relational schema. Prove or disprove the following statements. In each case you have to either indicate “yes”, or to indicate “no” and provide a set of functional dependencies and sets of attributes X and Y that violates the statement.
i.
X ⊆Y implies
X+ ⊆Y+.
ii.
X+ Ý Y+
= (X Ý Y) +
iii.
X+ Ü Y+
= (X Ü Y) +
b. [10 points] Find all minimal keys in the relation below and find all non-trivial functional dependencies satisfied by this relation.
|
A |
B |
C |
D |
|
1 |
1 |
1 |
1 |
|
1 |
1 |
1 |
2 |
|
2 |
1 |
1 |
1 |
|
1 |
2 |
1 |
3 |
|
2 |
2 |
2 |
4 |
3.
[30 points] Consider the following schema:
Product(id(4),
name(16), manufacturer(20), category(10), color(10), webpage(40))
Sales(pid(4), quantity(4), shippingaddress(20), date(12), shippingmethod(10))
Each attribute has a fixed length, with the size (in bytes)
indicated by the number in parentheses. The number of tuples in each relation
is:
T(Product) = 1,000,000
T(Sales) = 2,000,000
The size of one disk block is 1000 bytes, and there are 101 buffers available
in main memory.
a.
[5 points] Compute the number of blocks taken by each table:
B(Product) =
B(Sales) =
b.
[5
points] Consider the logical plan below:
Assume the following physical plan: the join is implemented as a block-nested
loop join, its result is pipelined into the selection operator, and, from
there, pipelined into the projection operators. Compute the total cost of this
physical plan.
c.
[10 points] Derive a new logical plan by pushing selections
and projections down as far as possible (you have to draw a plan).
d.
[10 points] Consider a physical plan for your new logical plan
in which all selections and projects are pipelined and the join is a
block-nested loop join. Further assume that 1% of all Products are in category “Gizmo”
and that 20% of all Sales have a quantity over 100. Compute the cost of your
plan.
4. [20 points] A database has five elements, X, Y, Z, U, V. The two questions below ask us to recover the database after a system crash
a.
<start T1> <T1,X,3> <start T2> <T2,Y,1> <start ckpt(T1,T2)> <T1,X,4> <start T3> <commit T1> <T2,Y,2> <T3,Z,5> <commit T2> <end ckpt> <start T4> <T4,U,8> <start ckpt(T3,T4)> <start T5> <T4,U,9> <T5,X,10> <commit T5> <start T6> <T6,Y,12>
[10 points] Assuming we maintain an undo log whose content,
after the crash, is:
Recover the database, assuming that after the crash the five elements have the
values below. Indicate which portion of the log you needed to inspect, and
which transactions have to be executed again.
X=1
Y=2
Z=3
U=4
V=5
b.
<start T1> <T1,X,3> <start T2> <T2,Y,1> <start T3> <T3,Z,5> <T2,Y,2> <commit T2> <start ckpt(T1,T3)> <T1,X,4> <start T4> <end ckpt> <commit T1> <T3,Y,2> <T4,U,8> <start ckpt(T3,T4)> <start T5> <T4,U,9> <T5,X,10> <commit T4> <start T6> <T6,Y,12>
[10 points] Assuming we maintain a redo log whose content,
after the crash, is:
Recover the database, assuming that after the crash the five elements have the
values below. Indicate which portion of the log you needed to inspect, and
which transactions have to be executed again.
X=1
Y=2
Z=3
U=4
V=5